package com.demo46_全排列;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {

    public List<List<Integer>> permute(int[] nums) {
        int[] used = new int[nums.length];
        // 初始化
        Arrays.fill(used,0);
        // 用来装路径元素的集合
        ArrayList<Integer> path = new ArrayList<>();
        // 用来装结果集合的集合
        List<List<Integer>> arrayLists = new ArrayList<>();

        // 递归
        dfs(nums,path,arrayLists,used);

        //返回结果
        return arrayLists;
    }

    private void dfs(int[] nums, ArrayList<Integer> path, List<List<Integer>> arrayLists, int[] used) {
        // 边界条件, 终止条件
        if (path.size()==nums.length){
            ArrayList<Integer> temp = new ArrayList<>();
            for (Integer item : path) {
                temp.add(item);
            }
            arrayLists.add(temp);

            return;
        }

        // 横向遍历 + 纵向递归
        for (int i = 0; i < nums.length; i++) {
            if (used[i]==0){
                // 处理当前元素
                path.add(nums[i]);
                used[i]=1;
                // 递归
                dfs(nums,path,arrayLists,used);
                // 回溯
                path.remove(path.size()-1);

                used[i]=0;
            }
        }
    }
}
